package leetcode_100;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *GenerateParentheses_22 给定正整数n 返回所有n对合法括号的String
 *describe:回溯 AC 100%
 *2018年12月22日 下午5:08:00
 */
public class GenerateParentheses_22 {
	public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<String>();
        dfs(res,0,0,new char[n*2],n);
        return res;
    }
	
	public void dfs(List<String> res,int index,int now,char []temp,int max) {
		if(index==temp.length) {
			res.add(new String(temp));
			return ;
		}
		if(max>0) {
			temp[index]='(';
			dfs(res,index+1,now+1,temp,max-1);
		}
		if(now>0) {
			temp[index]=')';
			dfs(res,index+1,now-1,temp,max);
		}
	}
}
